from LeetCoder import *


class Solution:
    def maximumOr(self, nums: List[int], k: int) -> int:
        n = len(nums) 
        r = [0] * n
        for i in range(n-2,-1,-1):
            r[i] = r[i + 1] | nums[i + 1]
        left = 0
        ans = 0
        for i in range(n):
            ans = max(ans,left | nums[i]<<k | r[i])
            left |=nums[i]
        return ans

        




s = Solution()
# print(s.maximumOr([41,79,82,27,71,62,57,67,34,8,71,2,12,93,52,91,86,81,1,79,64,43,32,94,42,91,9,25],10))
print(s.maximumOr(nums = [8,1,2], k = 2))
print(s.maximumOr(nums = [12,9], k = 1))

print(bin(12))
print(bin(9))

# print(bin(1000000000))
# print(len("111011100110101100101000000000"))

